#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<int,int,ll> Q;
const int P=6661;
static int C[P][P];
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
inline int com(ll n,ll m){
  if(n<P&&m<P)return C[n][m];
  return com(n/P,m/P)*C[n%P][m%P]%P;
}
int main(){
  freopen("izumi.in","r",stdin);
  freopen("izumi.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=C[0][0]=1;i<P;i++)
    for(int j=C[i][0]=1;j<=i;j++)
      C[i][j]=add(C[i-1][j],C[i-1][j-1]);
  int n,q; ll k; cin>>n>>q>>k;
  vector<int> a(n);
  for(int i=0;i<n;i++)
    a[i]=com(k,i+1);
  if(n>1e5){
    vector<Q> v;
    while(q--){
      int op,l,r; cin>>op>>l>>r,l--,r--;
      if(op==1){
        ll x; cin>>x,v.emplace_back(l,r,x);
      }
      else{
        if(!v.empty()){
          reverse(v.begin(),v.end());
          set<int> s;
          for(int i=0;i<n;i++)
            s.emplace(i);
          for(int i=0;i<v.size();i++){
            int l,r; ll x; tie(l,r,x)=v[i];
            for(auto it=s.lower_bound(l);it!=s.end()&&*it<=r;it=s.erase(it))
              a[*it]=com(x,*it-l+1);
          }
          partial_sum(a.begin(),a.end(),a.begin(),add);
          v.clear();
        }
        cout<<add(a[r],l?P-a[l-1]:0)<<'\n';
      }
    }
    return 0;
  }
  while(q--){
    int op,l,r; cin>>op>>l>>r,l--,r--;
    if(op==1){
      ll x; cin>>x;
      for(int i=l;i<=r;i++)
        a[i]=com(x,i-l+1);
    }
    else{
      int c=0;
      for(int i=l;i<=r;i++)
        self_add(c,a[i]);
      cout<<c<<'\n';
    }
  }
  return 0;
}